package algorithm.arrayAlgorithm;

/**
 * @ClassName: MaxDistance
 * @Description 1162. 地图分析
 * <p>
 * 你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域最远的海洋区域是是哪一个吗？请返回该海洋区域到离它最近的陆地区域的距离。
 * <p>
 * 我们这里说的距离是『曼哈顿距离』（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。
 * <p>
 * 如果我们的地图上只有陆地或者海洋，请返回 -1。
 * @Author skywingking
 * @Date 2022/1/9 7:39 下午
 **/
public class MaxDistance {
    public int maxDistance(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int result = -1;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 0) {
                    result = Math.max(result, getMinLandDistance(i, j, grid));

                }
            }
        }
        return result;
    }

    private int getMinLandDistance(int x, int y, int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int distance = 1;
        while (true) {
            for (int n = 0; n <= distance; n++) {
                if ((x - n >= 0) && (y - distance + n >= 0) && grid[x - n][y - distance + n] == 1) {
                    return distance;
                }
                if ((x - n >= 0) && (y + distance - n < grid[x - n].length) && grid[x - n][y + distance - n] == 1) {
                    return distance;
                }
                if ((x + n < grid.length) && (y - distance + n >= 0) && grid[x + n][y - distance + n] == 1) {
                    return distance;
                }
                if ((x + n < grid.length) && (y + distance - n < grid[x + n].length) && grid[x + n][y + distance - n] == 1) {
                    return distance;
                }
            }
            if (distance > (x + y) && distance > (grid.length - x + y) && distance > (x + grid[x].length - y) && distance > (grid.length + grid[x].length - x - y)) {
                return -1;
            }
            distance++;
        }
    }
}